Digitally-formatted still graphic images are popular items among users of public on-line information services. These services allow users to select from large numbers of digitized images, and to download the selected images for viewing on the user's own computer. The availability and widespread use of high-resolution computer displays has increased the demand for high-quality digitized images.
Despite the widespread availability of digitized images for downloading, finding and obtaining useful images can be a frustrating experience. This is due primarily to the large amount of data required to represent a high-resolution computer image and to the corresponding length of time required to download such an image to an individual's personal computer using conventional telecommunication techniques. Although data compression is commonplace, high-resolution images can still take several minutes to transfer.
For instance, a true-color 640 by 480 pixel image, represented by 24 data bits per image pixel, takes at least 12 minutes to transfer using a 9600 baud modem. Common data compression techniques can reduce this time to perhaps one to two minutes. Even this delay, however, can be very frustrating. Compounding the frustration is the very likely possibility that the image, once it is transferred and viewed, will turn out to be something quite different than what the user expected or desired. Downloading and screening a number of images can easily take hours.
Progressive image transmission is a technique used to reduce this frustration to some degree. It allows a receiving computer to quickly display a very low-resolution representation of the image being downloaded. As more and more data is obtained by the user's computer, the image is displayed at ever-increasing levels of resolution. The user can terminate the transfer at any point if the image appears to be unusable.
Discrete wavelet transformation is a recently developed technique which has been used to compress still image data and to also facilitate progressive image transmission. Several authors have described methods for compressing and transmitting still image data using discrete wavelet transformation. See, for example, the following articles, which are hereby incorporated by reference:
A. Mallat, Stephane G., "A Theory for Multiresolution Signal Decomposition: The Wavelet Representation", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 7, pp. 674-692 (July 1989) PA0 B. Zettler, William R., et al., "Application of Compactly Supported Wavelets to Image Compression", Aware Technical Report AD900119, pp. 1-9 (1991) PA0 C. Antonini, Marc, et al., "Image Coding Using Wavelet Transform", IEEE Transactions On Image Processing, Vol. 1, No. 2, pp. 205-220 (April 1992) PA0 D. Shapiro, Jerome M., "An Embedded Hierarchical Image Coder Using Zerotrees Of Wavelet Coefficients", IEEE Proceedings of Data Compression Conference, pp. 214-223 (1993) PA0 E. Blanford, Ronald P., "Wavelet Encoding and Variable Resolution Progressive Transmission", NASA Space and Earth Science Data Compression Workshop, pp. 25-35 (1993) PA0 A. Baaziz, Nadia, et al., "Laplacian Pyramid Versus Wavelet Decomposition for Image Sequence Coding", IEEE International Conference On Acoustics, Speech and Signal Processing, pp. 1965-1968, (1990) PA0 B. Vetterli, Martin, et al., "Wavelets and Filter Banks: Relationships and New Results", IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1723-1726, (1990) PA0 C. Press, William H., "Wavelet Transforms: A Primer", Center for Astrophysics, Preprint Series No. 3184, pp. 1-24 PA0 D. Cody, Mac A., "The Fast Wavelet Transform--Beyond Fourier Transforms", Dr. Dobb's Journal, pp. 16-28; 100-101, (April 1992) PA0 E. Rioul, Olivier, et al., "Wavelets and Signal Processing", IEEE Signal Processing Magazine, pp. 14-38, (October 1991) PA0 F. Mallat, Stephane G., "A Compact Multiresolution Representation: The Wavelet Model", IEEE Proceedings of Workshop on Computer Vision, pp. 2-7, (1987) PA0 G. Mallat, S. G., "Multiresolution Approach To Wavelets In Computer Vision", Proceedings of the International Conference, Marseille, France, pp. 313-327 (December, 1987) PA0 H. Daubechies, Ingrid; Vetterling, William T.; Teukolsky, Saul A.; Society for Industrial and Applied Mathematics, "The What, Why, and How of Wavelets", Ten Lectures on Wavelets, Chapter 1, pp. 1-16 (1992)
In addition to the articles cited above, the following articles, also incorporated by reference, give more general descriptions of discrete wavelet transforms:
As explained by Zettler et al. at pages 2-4 of their article entitled "Application of Compactly Supported Wavelets to Image Compression," the term wavelet refers to an orthonormal basis for L.sup.2 (R), the square-integrable function on the real line, which is defined recursively from a set of scaling function coefficients EQU {a.sub.k : k.epsilon.{0, . . . , 2N-1},N.epsilon.Z.sup.+,a.sub.k .epsilon.R }
that satisfies the following conditions EQU .SIGMA.a.sub.k =2 EQU .SIGMA.a.sub.k.sup.2 =2
and more generally, EQU .SIGMA.a.sub.k a.sub.k+2l =2.delta..sub.0l
As further explained by Zettler et al., there are infinitely many sets a.sub.k for N.gtoreq.2 that satisfy these conditions. These coefficients implicitly define a scaling function .phi.(x) satisfying the following recursion: EQU .phi.(x)=.SIGMA.a.sub.k .phi.(2x-k) k.epsilon.{0, . . . , 2N-1}
The scaling functions, their translates, the associated fundamental wavelet function .PSI.(x), and scaled translates of .PSI. form an orthonormal basis for L.sup.2 (R). The wavelet function .PSI. is defined in terms of the scaling function as EQU .PSI.(x)=.SIGMA.(-1).sup.k)i a.sub.k+1 .phi.(2x+k) k.epsilon.{-1, . . . , 2N-2}
In one dimension, the discrete wavelet transform produces, from an input sequence X={x.sub.i }, two output sequences (with k.epsilon.{0, . . . , 2N-1}): ##EQU1## Since the discrete wavelet transform is invertible, it provides perfect reconstruction. Several variations of wavelet transformations, using the general principles described above, have been described in the articles cited.
Image data compression using discrete wavelet transforms begins by decomposing or transforming an image into four subbands or subimages using the above equations. Each subimage is one fourth the size of the original image, and contains one fourth as many data points as the original image. The image decomposition involves first performing a one-dimensional wavelet convolution on each horizontal pixel column of the original image, thereby dividing the image into two subimages containing low frequency and high frequency information respectively. The same or a similar convolution is then applied to each vertical pixel row of each subimage, dividing each of the previously obtained subimages into two further subimages which again correspond to low and high frequency image information. The resulting four subimages can be referred to as LL, LH, HL, and HH subimages. The LL subimage is the one containing low frequency information from both the vertical and horizontal wavelet convolutions. The LH subimage is the one containing low frequency image information from the horizontal wavelet convolution and high frequency image information from the vertical wavelet convolution. The HL subimage is the one containing high frequency information from the horizontal wavelet convolution and low frequency image information from the vertical wavelet convolution. The HH subimage is the one containing high frequency information from both the vertical and horizontal wavelet convolutions.
The result of this process is graphically illustrated in FIGS. 1 and 2. FIG. 1 shows an original, uncompressed still image 10. FIG. 2 shows a first decomposition level 12 of the same image. Decomposition level 12 is the result of transforming the still image of FIG. 1 using vertical and horizontal passes of a discrete wavelet transform as described above. Decomposition level 12 includes four subimages which are compositely grouped for purposes of illustration. The subbands or subimages of this first decomposition level are designated as the LL1, LH1, HL1, and HH1 subimages, in accordance with the nomenclature already given, with the suffix 1 indicating the first decomposition level. The LL1 subimage contains the low frequency information from the original image. Note that subimage LL1, when represented on a screen display, appears like the original image except at a lower resolution or size. The LH1 subimage contains high frequency information occurring in a vertical direction. The HL1 subimage contains high frequency information occurring in a horizontal direction. The HH1 subimage contains high frequency information occurring in a diagonal direction. In combination, the four subimages contain all the information necessary to reconstruct the original image.
The first decomposition level can be further decomposed to include a second decomposition level 14 as shown in FIG. 3. This further decomposition is performed only on subimage LL1 of first decomposition level 12. To decompose subimage LL1, horizontal and vertical wavelet convolutions are performed on subimage LL1 in the same manner as the same operations have already been performed on the original image. This step subdivides subimage LL1 into LL2, LH2, HL2, and HH2 subimages. Again, subimage LL2 looks like the original image, except that it has a much lower resolution. Specifically, the LL subimage at each decomposition level has one fourth as many data points as the LL subimage of the next higher decomposition level.
The wavelet transforms described above are performed recursively on each successively obtained LL subimage. For the practical purposes to be accomplished by the invention described below, it has generally been found that calculating four or five decomposition levels is sufficient.
To reconstruct the original image, the inverse wavelet transform is performed recursively at each decomposition level. Assuming a two-level compression scheme, the second decomposition level contains a subimage LL2 which is a low resolution or base representation of the original still image. To obtain a higher resolution, subimage LL1 is reconstructed by performing an inverse wavelet transform using the subimages of the second decomposition level. The original image, at the highest available resolution, can subsequently be obtained by performing the inverse transform using the subimages of the first decomposition level (but only after obtaining subimage LL1 through an inverse transform of the second decomposition level).
The attractiveness of the wavelet approach to image transmission is that subimages LH, HL, and HH contain data which can be efficiently compressed to very high compression ratios through such methods as run-length and Huffman encoding. The preferred embodiments of the invention retain this advantage. In addition, the invention provides efficient methods of storing and transmitting still image data to allow the image to be quickly reconstructed and displayed, at ever-increasing resolutions, for early user evaluation. If the still image is found by the user to be unacceptable at any time during transmission, the transmission and reconstruction can be aborted before significant time is wasted.